﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution51
{
    IList<IList<string>> res= new List<IList<string>>();
    public IList<IList<string>> SolveNQueens(int n)
    {
        char[][] path= new char[n][];
        for (int i = 0; i < n; i++)
        {
            path[i]=new char[n];
            for (int j = 0; j < n; j++)
            {
                path[i][j] = '.';
            }
        }

        DFS(path,n,0);

       return res;

    }

    private void DFS(char[][] path, int n,int row)
    {
      

        if (row == n)
        {
            IList<string> cur = new List<string>();
            for (int i = 0; i < path.Length; i++)
            {
               string str=new string(path[i]);
                
                cur.Add(str);
            }

            res.Add(cur);
            return;
        }
        for(int i = 0;i < n;i++)//这里的回溯已经保证同一行不会出现了
        {

            if (Vaild(path,n, row, i))
            {
                path[row][i] = 'Q';//这个为Q

                

                DFS(path,n, row + 1);
                path[row][i] = '.';//回溯

            }
         

        }
    }

    private bool Vaild(char[][] path, int len,int row, int col)
    {
        //上下左右
        //上
        //if(row-1>=0&& path[row - 1][col] == 'Q')
        //{
        //    return false;
        //}
        ////下
        //if (row + 1 < len && path[row +1][col] == 'Q')
        //{
        //    return false;
        //}
        //上下一起，同一行都不行

        for(int i = 0; i < row; i++)
        {
            if (i != row)
            {
                if (path[i][col] == 'Q')
                {
                    return false;
                }

               

            }
            //左上斜
            int leftUpCol = col - (row - i);
            if(leftUpCol >= 0 && path[i][leftUpCol] == 'Q')
            {
                return false;
            }
            if (col + (row - i)<len && path[i][col + (row - i)] == 'Q')
            {
                return false;
            }

        }


        ////右
        //if (col + 1 < len && path[row ][col + 1] == 'Q')
        //{
        //    return false;
        //}
        ////左
        //if (col - 1 >=0 && path[row ][col - 1] == 'Q')
        //{
        //    return false;
        //}
        //左上

       

        return true;
    }
}
class Program51 { 

static void Main51(string[] args) { 
    
    Solution51 solution = new Solution51();
        IList<IList<string>> res= solution.SolveNQueens(4);

        for (int i = 0; i < res.Count; i++)
        {
            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j]+",");
            }
            Console.WriteLine();
        }
    
    }

}


